//
//  Vector_sort.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/6.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

/// 排序
extension Vector where Element: Comparable {
    
    /// 就地排序
    public func sort() {
        _sort(from: 0, to: _size)
    }
    
    public func sort(at range: CountableRange<Index>) {
        _sort(from: range.lowerBound, to: range.upperBound)
    }
    
    public func sort(at range: CountableClosedRange<Index>) {
        _sort(from: range.lowerBound, to: range.upperBound.advanced(by: 1))
    }
}

extension Vector where Element: Comparable & Cloneable {
    
    /// 返回当前Vector的已排序版本
    public func sorted() -> Vector<Element> {
        let copy = clone()
        copy.sort()
        return copy
    }
    
    public func sorted(at range: CountableRange<Index>) -> Vector<Element> {
        let copy = clone()
        copy.sort(at: range)
        return copy
    }
    
    public func sorted(at range: CountableClosedRange<Index>) -> Vector<Element> {
        let copy = clone()
        copy.sort(at: range)
        return copy
    }
}

extension Vector where Element: Comparable {
    func _sort(from startIndex: Index, to endIndex: Index) {
        #if false
//        _bubbleSort(from: startIndex, to: endIndex)
        _insertionSort(from: startIndex, to: endIndex)
        #else
        _quickSort(from: startIndex, to: endIndex)
//        _mergeSort(from: startIndex, to: endIndex)
        #endif
    }
    
    func _bubbleSort(from startIndex: Index, to endIndex: Index) {
        for i in startIndex..<endIndex {
            for j in (startIndex + 1)..<(endIndex - i) {
                if _storage[j - 1] > _storage[j] {
                    swap(&_storage[j - 1], &_storage[j])
                }
            }
        }
    }
    
    /// not a in-place sort, but stable
    func _mergeSort(from startIndex: Index, to endIndex: Index) {
        // 不足两个元素自然有序
        if endIndex - startIndex < 2 { return }
        // 递归分解 直至分解为单个自然有序的区间
        let midIndex = ((startIndex + endIndex).toDouble() / 2).toInt()
        _mergeSort(from: startIndex, to: midIndex)
        _mergeSort(from: midIndex, to: endIndex)
        // 合并
        _merge(startIndex, midIndex, endIndex)
    }
    
    func _merge(_ startIndex: Index, _ midIndex: Index, _ endIndex: Index) {
        // start..<mid这一段的首地址和长度
        let firstPart = _storage + startIndex
        let fsize = midIndex - startIndex
        // mid..<end这一段的首地址和长度
        let secondPart = _storage + midIndex
        let ssize = endIndex - midIndex
        // 拷贝前半部分
        let copyPart = Allocator.allocate(fsize, for: Element.self)
        for i in 0..<fsize { copyPart[i] = firstPart[i] }
        // 将copyPart和second都合并到first中
        // i控制first中已处理元素的位置
        // j和k分别控制copyPart和second中已处理元素的位置
        var i = 0, j = 0, k = 0
        // copyPart和second全部处理完毕退出循环
        while j < fsize || k < ssize {
            // 利用||短路求值特性
            // j < fsize, copyPart中仍有元素
            // k >= ssize, 若满足，说明secondPart中的元素已经全部合并
            // 此时只需要把copyPart的中剩余的元素一次放入firstPart就可以
            // 若不满足，说明secondPart也还有元素，此时就需要比较其相对大小
            if (j < fsize) && (k >= ssize || copyPart[j] <= secondPart[k]) {
                firstPart[i] = copyPart[j]
                i += 1
                j += 1
            }
            if (k < ssize) && (j >= fsize || secondPart[k] < copyPart[j]) {
                firstPart[i] = secondPart[k]
                i += 1
                k += 1
            }
        }
        // 释放临时内存
        copyPart.deallocate()
    }
    
    func _insertionSort(from startIndex: Index, to endIndex: Index) {
        if endIndex - startIndex < 2 { return }
        /// 整个空间看成两部分
        /// 前半段是已排序区间
        /// 后半段是未排序区间
        /// 每次从未排序区间内提取一个元素直至结束
        for i in (startIndex + 1)..<endIndex {
            for j in 0..<i {
                /// 0..<i的区间是已排序的
                /// 逐个比对 直至找到_storage[i]在已排序区间的合适位置
                if _storage[i] < _storage[j] {
                    #if true
                    swap(&_storage[i], &_storage[j])
                    #else
                    // Note: 使用元组交换位置
                    (_storage[i], _storage[j]) = (_storage[j], _storage[i])
                    #endif
                }
            }
        }
    }
    
    /// in-place, but not stable
    func _quickSort(from startIndex: Index, to endIndex: Index) {
        if endIndex - startIndex < 2 { return }
///       partitioning之后 _storage[pivotIndex]已经在正确的位置上
        #if false
        // 随机选取pivot
        let initialIndex = _randomPivotIndex(from: startIndex, to: endIndex)
        // Lomoto算法轴点是最后一个元素 所以交换一下这两个元素的位置
        (_storage[endIndex - 1], _storage[initialIndex]) = (_storage[initialIndex], _storage[endIndex - 1])
        let pivotIndex = _partitionLomuto(from: startIndex, to: endIndex)
        #else
        // 随机选取pivot
        let initialIndex = _randomPivotIndex(from: startIndex, to: endIndex)
        // Hoare算法轴点是第一个元素 所以交换一下这两个元素的位置
        (_storage[startIndex], _storage[initialIndex]) = (_storage[initialIndex], _storage[startIndex])
        let pivotIndex = _partitionHoare(from: startIndex, to: endIndex)
        #endif
        // 递归此过程直至退化到平凡情况
        _quickSort(from: startIndex, to: pivotIndex)
        _quickSort(from: pivotIndex + 1, to: endIndex)
    }
    
    /// Lomoto算法将_storage分为四部分
    /// startIndex...i 中的元素都严格 <= pivot
    /// i+1..j-1 中的元素都严格 > pivot
    /// j...endIndex-2是还未比对的
    /// endIndex-1永远是pivot
    func _partitionLomuto(from startIndex: Index, to endIndex: Index) -> Index {
        let pivot = _storage[endIndex - 1]
        var i = startIndex
        for j in i..<(endIndex - 1) {
            if _storage[j] <= pivot {
                // _storage[j]和_storage[i]有可能是同一个元素(因此不用带inout参数的swap)
                (_storage[i], _storage[j]) = (_storage[j], _storage[i])
                i += 1
            }
        }
        // 候选轴点归位
        (_storage[i], _storage[endIndex - 1]) = (_storage[endIndex - 1], _storage[i])
        return i
    }
    
    func _partitionHoare(from startIndex: Index, to endIndex: Index) -> Index {
        // 取起始元素为轴点
        // 接下来的任务就是将原数组分为<=轴点和>=轴点两部分
        let pivot = _storage[startIndex]
        // <=轴点部分的起始位置
        var i = startIndex
        // >=轴点部分的起始位置
        var j = endIndex - 1
        // 循环至只剩下轴点
        // 循环退出 i == j 此时i/j就是轴点应处的位置
        while i < j {
            // 首先从 >= 轴点的部分开始
            // 因为pivot已经取出保存好
            // 可以认为pivot已从数组中删除
            // 如果_storage[j] >= pivot
            // 使j--，也就是往左扩充>=轴点的部分
            while i < j && _storage[j] >= pivot {
                j -= 1
            }
            // 退出上个while循环 则有_storage[j] < pivot
            // 此时_storage[j]是属于<= pivot部分的
            // 又因为此前提过_storage[i]对应的元素已经被保存
            // 所以我们让 _storage[j]来占据这块空间
            // 赋值以后 空出来的空间就是_storage[j]了
            // 因为它被保存到_storage[i]中了
            _storage[i] = _storage[j]
            
            // 同上
            while i < j && _storage[i] <= pivot {
                i += 1
            }
            _storage[j] = _storage[i]
        }
        precondition(i == j, "\(i) should equal to \(j)")
        _storage[i] = pivot
        return i
    }
    
    func _randomPivotIndex(from startIndex: Index, to endIndex: Index) -> Index {
        return startIndex + Int(arc4random()) % (endIndex - startIndex)
    }
}
